package bak;

public class RadixInPlace
{
	public void radixSortInPlace(int[] arr, int startArr, int endArr,
			int startBit, int endBit, int bitRange)
	{
		if (startArr != endArr)
		{
			int counterNum = 1 << (endBit - startBit + 1);
			int[] counter = new int[counterNum];
			int[] lengthCounter = new int[counterNum];
			int[] bakCounter = new int[counterNum];

			long L = (long) Math.pow(2, endBit + 1) - 1;
			L = L >> startBit;
			L = L << startBit;

			// calculate count
			for (int i = startArr; i < endArr + 1; i++)
			{
				long value = arr[i] + (long) Integer.MAX_VALUE;

				value = value & L;

				value = value >> startBit;

				counter[(int) value]++;
			}

			// copy length info
			for (int i = 0; i < counter.length; i++)
			{
				lengthCounter[i] = counter[i];
			}

			// merge count
			for (int i = 1; i < counter.length; i++)
			{
				counter[i] = counter[i - 1] + counter[i];
			}

			// copy counter info
			for (int i = 0; i < counter.length; i++)
			{
				bakCounter[i] = counter[i];
			}

			// sort in place
			long value;
			int index = endArr;
			while (index >= startArr)
			{
				value = arr[index] + (long) Integer.MAX_VALUE;
				value = value & L;
				value = value >> startBit;

				int limit = bakCounter[(int) value] + startArr - 1;

				int desirePos = counter[(int) value] + startArr - 1;
				
				if (index > desirePos && index <= limit)
				{
					index--;
					continue;
				}
				else
				{
					swap(arr, index, desirePos);
					counter[(int) value]--;
				}
			}

			// recursive process
			int nuEndBit = startBit - 1;
			int nuStartBit = nuEndBit - bitRange + 1;
			if (nuEndBit >= 0 && nuStartBit >= 0)
			{
				int nuStartArr = startArr;
				int nuEndArr = startArr;
				for (int i = 0; i < counter.length; i++)
				{
					int length = lengthCounter[i];
					if (length > 0)
					{
						nuEndArr = nuStartArr + length - 1;
						radixSortInPlace(arr, nuStartArr, nuEndArr, nuStartBit,
								nuEndBit, bitRange);
						nuStartArr = nuEndArr + 1;
					}
				}
			}
			else if (nuEndBit >= 0 && nuStartBit < 0)
			{
				nuStartBit = 0;
				int nuStartArr = startArr;
				int nuEndArr = startArr;
				for (int i = 0; i < counter.length; i++)
				{
					int length = lengthCounter[i];
					if (length > 0)
					{
						nuEndArr = nuStartArr + length - 1;
						radixSortInPlace(arr, nuStartArr, nuEndArr, nuStartBit,
								nuEndBit, bitRange);
						nuStartArr = nuEndArr + 1;
					}
				}
			}
		}
	}

	private void swap(int[] arr, int pos1, int pos2)
	{
		try
		{
			int tmp = arr[pos1];
			arr[pos1] = arr[pos2];
			arr[pos2] = tmp;
		}
		catch (Exception ex)
		{
			System.out.println(pos1 + "\t" + pos2);
		}
	}

	public static void main(String[] args)
	{
		RadixInPlace r = new RadixInPlace();
		int arr[] = new int[10];
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		arr[3] = 3;
		arr[4] = 4;
		arr[5] = 5;
		arr[6] = 6;
		arr[7] = 7;
		arr[8] = 8;
		arr[9] = 9;

		r.radixSortInPlace(arr, 0, 9, 24, 31, 8);
	}
}
